package 每日一题OJ;

import java.util.*;

/**
 * @author shy_black
 * @date 2019/3/26 23:07
 * @Description:
 * 开辟左链表和右链表，以x为分割点当pHead.val < x时，
 * 将节点放入左链表中，否则放入右链表中
 * 最后将右链表挂到左链表后，返回左链表头结点即可。
 */
public class 链表分割 {

    class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            // write code here
            if (pHead == null || pHead.next == null)
                return pHead;
            ListNode l = new ListNode(-1);
            ListNode ltemp = l;
            ListNode r = new ListNode(-1);
            ListNode rtemp = r;
            while (pHead != null) {
                if (pHead.val < x) {
                    ltemp.next = pHead;
                    ltemp = ltemp.next;
                } else {
                    rtemp.next = pHead;
                    rtemp = rtemp.next;
                }
                pHead = pHead.next;
            }
            rtemp.next = null;
            ltemp.next = r.next;
            return l.next;
        }
    }
}